package com.tsx.leetcode.hot100.easy;

import com.tsx.leetcode.hot100.common.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Q94InorderTraversal {
    public static void main(String[] args) {
        Q94InorderTraversal q94InorderTraversal = new Q94InorderTraversal();
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        System.out.println(q94InorderTraversal.inorderTraversal(treeNode1));
    }

    //    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        dfs(res, root);
//        return res;
//    }
//
//    public void dfs(List<Integer> res, TreeNode root) {
//        if (root == null) {
//            return;
//        }
//        dfs(res, root.left);
//        res.add(root.val);
//        dfs(res, root.right);
//    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); // 模拟递归
        while (!stack.isEmpty() || root != null) { // 栈还没有空的时候
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }
}
